package com.njupt.DoublePoint;


/**
 * 面试题 02.07. 链表相交
 *  有问题
 */
public class GetIntersectionNode {


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

    public ListNode getIntersectionNode1(ListNode headA, ListNode headB){

        ListNode curA = headA;
        ListNode curB = headB;
        int countA = 0;
        int countB = 0;
        while(curA != null) {
            countA++;
            curA = curA.next;
        }
        while(curB != null) {
            countB++;
            curB = curB.next;
        }
        int temp;
        ListNode curTemp ;
        curA = headA;
        curB = headB;
        if(countB>countA){

            temp = countB;
            countB = countA;
            countA = temp;

            curTemp = curA;
            curA = curB;
            curB = curTemp;
        }
        int gap = countA-countB;
        while(gap-->0){
            curA = curA.next;
        }
        while(curA != null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }


    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(8);
        ListNode head3 = new ListNode(4);
        ListNode head4 = new ListNode(5);
        headA.next = head1;
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;


        ListNode headB = new ListNode(5);
        ListNode head5 = new ListNode(0);
        ListNode head6 = new ListNode(1);


        headB.next = head5;
        head5.next = head6;
        head6.next = head2;
        head2.next = head3;
        head3.next = head4;

        GetIntersectionNode test = new GetIntersectionNode();

        ListNode intersectionNode = test.getIntersectionNode1(headA, headB);
        System.out.println(intersectionNode.val);
    }
}
